/**
 * 插入排序， 就是抓起来一张牌， 然后， 把牌和之前抓的牌进行对比， 看看放在哪， 需要开辟新的控件
 */

// function insertSort(arr) {
//     const res = []
//     // 这里把第一个作为基准数据
//     res.push(arr[0])
//
//     for (let i=1; i< arr.length; i++) {
//         let a = arr[i]
//
//         for (let j = res.length -1; j >= 0; j--) {
//             let b = res[j]
//
//             if( a > b) {
//                 res.splice(j+1, 0, a)
//                 break;
//             }
//             if(j === 0) {
//                 res.unshift(a)
//             }
//         }
//     }
//     return res
// }
// const arr = [3, 9, 10, 2, 9, 0, 3, 2, 1]
//
// console.log(insertSort(arr));


function insertSortV2(arr) {
   const res = []
   res.push(arr[0])

    // 新获取的数据
    for (let i = 0; i <arr.length -1; i++) {
        const A = arr[i]

        // 依次和之前的数据比价 如果下于之前的 就放在前面
        for (let j = 0; j < res.length; j++) {
            const B = res[j]

            if( A > B) {
                res.splice(j+1, 0, A)
                // 跳出
                break;
            }
            // 如果是最小的， res中都没有这个小的 那就直接放到第一个
            if(j === 0) {
                // 如果比到了最前面， 那么就直接push进res数组。
                res.push(A)
            }
        }
    }
    return res;
}


const arr = [3, 9, 10, 2, 9, 0, 3, 2, 1]
console.log(insertSortV2(arr));
